Computer systems have long relied on communications between a control processor and remote terminals. More recently, communications also occur directly from terminal to terminal via a shared medium. In complex systems such as these, access to the medium must be carefully controlled to ensure not only that the system remains functional, but that it operates efficiently. Several methods have been developed to determine if terminals desire access to the medium and in what priority communication will be granted. Examples of typical methods are found in industry publications 802.5-1985 LANs: Token Ring Access (ANSI/IEEE); 802.4-1985 LANs:Token-Passing Bus (ANSI/EEE); 802.3-1985 LANs:CMSA-CD (ANSI/IEEE). U.S. Pat. Nos. include 4,672,604, 4,670,872, 4,667,193, 4,638,428, 4,598,363, 4,595,921, 4,577,184, 4,569,044, 4,475,121, 4,466,001, 4,454,508, 4,411,007, 4,385,314, 4,377,870, 4,365,267, 4,151,370, 4,149,144, 4,100,533, 4,088,983, 4,071,908, 4,038,641 and 3,795,895. Some of the methods discussed in these references only permit one terminal at a time to attempt access to the medium. Examples of this type of method are the token ring and token bus systems in which an electronic token is passed through the system, terminal by terminal, to determine communication status. If the terminal that possesses the token wishes to transmit, it is entitled to do so while all other terminals wait. If the terminal has nothing to transmit at that time, it passes the token to the next terminal. Although this permits a high degree of medium utilization when traffic is heavy, it is inefficient under light loading because the token must be passed through many terminals without carrying a message. If message type priorites are desired, the token must pass through all of the terminals without encountering a high priority request before a secondary priority transmission can begin, thereby incurring transmission delays (ref. U.S. Pat. No. 4,545,508 to Grow). Token ring is a form of loop communications because the terminals are connected together in a loop that permits the token to pass from terminal to terminal.
Another solution to communications medium control is typically called tree polling, branch polling, or probing. Here, a controller sends a message to a group of terminals located either logically (by address) or physically (in a tree topology network) along a particular branch of the network. Every service requesting terminal that is in the selected branch responds to the controller. The controller can manage network priorities through control of the set of terminals tested by each choice of branch. The advantage of this system is that it allows the controller to determine quickly the extent of service needed from a large group of terminals at one time. The drawback of this type of polling is collisions. A collison occurs when two or more signals from terminals arrive simultaneously at the controller. When this occurs, the resulting message is usually garbled. One method of resolving collisions is to reduce the branch size and poll again. This branch reduction process continues until no collisions occur, which is assured because the smallest branch size includes only one terminal. In a heavily loaded network, branch polling is far less effective than even a simple round robin polling scheme, because multiple polls plus collision detection overhead are required to select a single terminal. Adaptive polling or probing techniques have been developed to adapt to heavy or light conditions, such as that described in U.S. Pat. No. 4,071,908 to Brophy et. al. However, these methods still involve the inefficiency of multiple polling sequences, each sending polling words that contain entire addresses and other data to select a single terminal.
Another method for avoiding collisions is disclosed in U.S. Pat. No. 4,595,921 to Wang et. al., which spaces the terminals at a unique distance from the controller. Since each terminal is at a unique distance, the signals from them can never arrive at the same time. This method works for small numbers of terminals in close proximity, but becomes unwieldy for greater distances and terminal counts.
Another methodology that experiences collision problems is Carrier Sense Multiple Access with Collision Detection (CSMA/CD) and similar methods in which terminals desiring access to the medium simply attempt, upon demand, to transmit a message to the desired recipient. This method is vulnerable to saturation problems in the same manner that branch polling is.
The common method of dealing with collisions in either branch polling or CSMA/CD type schemes is called "collision detection and avoidance". In this scheme, if a collision is detected, i.e. a garbled message is received because of overlapping bit streams, the terminals retransmit after a random time delay. The theory is that the two or three colliding terminals will retransmit at different times, thereby avoiding a collision. While this method will work when systems are lightly loaded, collisions increase as the communications traffic builds. Even with the time delays, collision will increase until saturation occurs and all communication breaks down because every message results in a collision and all communication halts. Currently, many communications networks experience difficulties with collision saturation, especially those having high message volume devices like file servers.
In addition to the above problems, the methods that require specific topologies such as bus, star or ring, are not applicable to open area control situations, such as management of infrared wall bounce systems, or control of mobile terminals. Ring or tree topology networks also have the drawback that transmission delays, due to the requirement to store portions of or complete messages prior to passing them on, are introduced in each active branching node.